import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int[] arr=new int[100001];
        arr[0]=1;
        arr[1]=1;
        for(int i=2;i<arr.length;i++){
            arr[i]=(arr[i-1]+arr[i-2])%1000000;
        }
        while (scanner.hasNext()){
            int n=scanner.nextInt();
            System.out.printf((n<25?"%d\n":"%06d\n"),arr[n]);
        }
    }
}






















//public class Main {
//    public static void main(String[] args) {
//        Scanner scanner=new Scanner(System.in);
//        int[] arr=new int[]{31,30,31,30,31,30,31,31,30,31,30,31};
//        while (scanner.hasNext()){
//            int year1=scanner.nextInt();
//            int month1=scanner.nextInt();
//            int day1=scanner.nextInt();
//            int year2=scanner.nextInt();
//            int month2=scanner.nextInt();
//            int day2=scanner.nextInt();
//            int money=getMoney(year1)-getThisMoney(year1,month1,day1-1);
//            money+=getThisMoney(year2,month2,day2);
//            if(year1==year2){
//                money-=getMoney(year1);
//            }
//            for(int i=year1+1;i<year2;i++){
//                money+=getMoney(i);
//            }
//            System.out.println(money);
//        }
//    }
//    public static int getMoney(int year){
//        return 2*31+1*28+1*31+2*30+1*31+2*30+1*31+2*31+2*30+2*31+1*30+2*31+(LeapYear(year)?1:0);
//    }
//
//    public static boolean LeapYear(int year){
//        return year%400==0||(year%4==0&&year%100!=0);
//    }
//
//    public static int getThisMoney(int year,int month,int day){
//        int money=0;
//        if(!judge(month)){
//            money=day*2;
//        }else{
//            money=day;
//        }
//
//        while (--month>0){
//            if(month==1||month==8||month==10||month==12){
//                money+=62;
//            }else if(month==3||month==5||month==7){
//                money+=31;
//            }else if(month==4||month==6||month==9){
//                money+=60;
//            }else if(month==11){
//                money+=30;
//            }else{
//                money+=(28+(LeapYear(year)?1:0));
//            }
//        }
//        return money;
//    }
//    public static boolean judge(int month){
//        return month==2||month==3||month==5||month==7||month==11;
//    }
//
//}
